package com.maptasksolver.struct.heap;

import java.io.PrintWriter;

import com.maptasksolver.exceptions.EmptyTreeException;
/**
 * @author MDE
 * @version Minimum heap
 */

public class HeapMin {
	
	BinTree tree;
	
	public void add(Treeable node) {
		if (tree == null) {
			tree = new BinTree(node);
			return;
		}
		goToRoot();
		boolean l = tree.hasLeftSon(), r = tree.hasRightSon();
		while (l && r) {
			if (tree.getSonsLeft() < tree.getSonsRight()) {
				tree.incSon(BinTreeSons.Left);
				tree = tree.getLeftSon();				
			}
			else {
				tree.incSon(BinTreeSons.Right);
				tree = tree.getRightSon();
			}
				
			l = tree.hasLeftSon();
			r = tree.hasRightSon();
		}
		
		BinTreeSons connection = tree.hasLeftSon() ? BinTreeSons.Right : BinTreeSons.Left;
		
		BinTree newNode = new BinTree(node);
		newNode.connectToTreeAs(tree, connection);
		if (connection == BinTreeSons.Left)
			tree = tree.getLeftSon();
		else
			tree = tree.getRightSon();
		pushUp();
	}
	
	public Treeable Pop() throws EmptyTreeException {
		if (isEmpty()) throw new EmptyTreeException();
		
		goToRoot();
		Treeable res = tree.getNode().clone();
		
		BinTreeSons son = BinTreeSons.Right;
		
		while (tree.hasLeftSon() || tree.hasRightSon()) {			
			if (tree.hasLeftSon() && tree.hasRightSon())
				if (tree.getLeftSon().getValue() < tree.getRightSon().getValue()) {
					tree = tree.getLeftSon();
					tree.swapWithFather();
					tree = tree.getRightSon();
					son = BinTreeSons.Left;
				} else {
					tree = tree.getRightSon();
					tree.swapWithFather();
					tree = tree.getLeftSon();
					son = BinTreeSons.Right;
				}
			else if (tree.hasLeftSon()) {
				tree = tree.getLeftSon();
				tree.swapWithFather();
				tree = tree.getLeftSon();
				son = BinTreeSons.Left;
			} else if (tree.hasRightSon()) {
				tree = tree.getRightSon();
				tree.swapWithFather();
				tree = tree.getRightSon();
				son = BinTreeSons.Right;
			}
		}
		
		if (tree.hasFather())
			tree.getFather().deleteSon(son);
		else {
			tree = null;
			return res;
		}
		
		return res;
	}
	
	public boolean isEmpty() {
		return tree == null;
	}
	
	public int getCount() {
		if (isEmpty()) return 0;
		goToRoot();
		return tree.getSonsLeft() + tree.getSonsRight() + 1;
	}
	

	public double getMin() throws EmptyTreeException {
		if (isEmpty()) throw new EmptyTreeException();
		goToRoot();
		return tree.getValue();
	}
	
	public boolean checkTree() {
		if (isEmpty()) return true;
		
		boolean l = tree.hasLeftSon(),  r = tree.hasRightSon();		
		
		if (!l && !r) return true;
		
		double value = tree.getValue();
		
		if (l && tree.getLeftSon().getValue() < value) return false;
		if (r && tree.getRightSon().getValue() < value) return false;
		
		boolean checkL = true, checkR = true;		
		
		if (l) {
			tree = tree.getLeftSon();
			checkL = checkTree();
			tree = tree.getFather();
		}
		
		if (r) {
			tree = tree.getRightSon();
			checkL = checkTree();
			tree = tree.getFather();
		}
		
		return checkL && checkR;
	}
	
	public void outputTree(PrintWriter file) {		
		goToRoot();
		
		outputNode(file);		
		file.println();
	}	
	
	private void outputNode(PrintWriter file) {
		if (tree == null) return;
		file.print("(" + tree.getValue() + ", L:  " + 
				tree.getSonsLeft() + 
				", R: " + tree.getSonsRight()  + ") ");
		
		if (tree.hasLeftSon()) {
			file.print("Go left ");
			tree = tree.getLeftSon();
			outputNode(file);
			file.print("Go up ");
			tree = tree.getFather();
		}
		
		if (tree.hasRightSon()) {
			file.print("Go right ");
			tree = tree.getRightSon();
			outputNode(file);
			file.print("Go up ");
			tree = tree.getFather();
		}
	}
	
	private void pushUp() {
		if (tree.hasFather()) {
			if (tree.getFather().getValue() < tree.getValue()) return;
			tree.swapWithFather();
			pushUp();
		}
	}
		
	private void goToRoot() {
		if (tree != null)
			while (tree.hasFather()) 
				tree = tree.getFather();
	}
	
}
